#!/usr/bin/env python
#encoding: latin1

from collections import deque
import classgrafo
import quicksort

def adynodo_in_adypadre(nodo, padre):
	"""Pre:Recibe un nodo clase nodo y un padre clase nodo. Padre es adyacentes de nodo y nodo es adyacente de padre.
	Post: Devuelve True si los adyacentes de nodo son adyacentes a padre o el único adyacente a nodo es el padre"""
	adyacentes_padre = {}
	for nodo_aux in padre.adyacentes():
		adyacentes_padre[nodo_aux] = ""

	for nodoady in nodo.adyacentes():
		if (nodoady == padre) or (nodoady in adyacentes_padre):
			continue
		else:
			return False
	return True

def calcular_influencia(grafo, caminos):
	cantidad_caminos = {}
	nodos_visitados = []	

	for camino in caminos:
		for nodo in camino[1:-1]: # Excluyo al primero y ultimo nodo
			if nodo.numero() not in cantidad_caminos:
				cantidad_caminos[nodo.numero()] = 1
				nodos_visitados.append(nodo)
			else:
				cantidad_caminos[nodo.numero()] += 1

	for nodo in nodos_visitados:
		nodo.influencia += cantidad_caminos[nodo.numero()] / float(len(caminos))

def calcular_punto_1(grafo):
	print "1- Popularidad (grado de entrada de cada nodo):"
	quicksort.quick_sort(grafo.nodos, classgrafo.comparar_grado_entrada)
	for nodo in grafo.nodos:
		print nodo.nombre() + ": " + str(nodo.grado_entrada())

def calcular_punto_2(grafo):
	print "2- Influencia de cada nodo:"

	# Inicializo la influencia de todos los nodos en cero
	for nodo in grafo.nodos:
		nodo.influencia = 0

	for nodo_i in grafo.nodos:
		cola = deque()
		cola.append(nodo_i)
		
		caminos_minimos = {} # Diccionario que contiene para cada nodo, una lista con todos los caminos minimos que llegan hasta él
		distancias = {} # Diccionario que contiene para cada nodo, la distancia

		for nodo_j in grafo.nodos:
			caminos_minimos[nodo_j.numero()] = []
			distancias[nodo_j.numero()] = -1
      
		distancias[nodo_i.numero()] = 0
		camino_minimo_i = [nodo_i]
		caminos_minimos[nodo_i.numero()].append(camino_minimo_i)

		while len(cola) > 0:
			nodo_k = cola.popleft()
			for nodo_ady in nodo_k.adyacentes():
				if distancias[nodo_ady.numero()] == -1:
					cola.append(nodo_ady) # Primera vez que se visita el nodo, se encola
					distancias[nodo_ady.numero()] = distancias[nodo_k.numero()] + 1

				if distancias[nodo_ady.numero()] == distancias[nodo_k.numero()] + 1:
					# Copio los caminos minimos y agrego el nodo que está visitando
					for camino_minimo in caminos_minimos[nodo_k.numero()]:
						camino_minimo_nuevo = list(camino_minimo)
						camino_minimo_nuevo.append(nodo_ady)
						caminos_minimos[nodo_ady.numero()].append(camino_minimo_nuevo)

		for nodo_j in grafo.nodos:
			if nodo_j != nodo_i and len(caminos_minimos[nodo_j.numero()]) > 0:
				calcular_influencia(grafo, caminos_minimos[nodo_j.numero()])
  
	quicksort.quick_sort(grafo.nodos, classgrafo.comparar_influencia)
	for nodo in grafo.nodos:
		print nodo.nombre() + ": " + str("%.2f" % nodo.influencia)

def calcular_punto_3(grafo): 
	"""Pre: El grafo no puede estar vacio"""
		
	print"3-Recomendaciones para:" 

	for nodo in grafo.nodos: 
		adyacentes_de_nodo = {}
		for nodoadyacente in nodo.adyacentes():
			adyacentes_de_nodo[nodoadyacente] = ""

		if (len(nodo.adyacentes()) == 0): #Caso que no tiene adyacentes. (Si no tiene amigos, no se le recomienda nadie)
			continue
		contador_recomendado = 0
		nodo_recomendado = grafo.get_nodo_vacio()
		for nodoady_para_comparar in nodo.adyacentes():			
			if (not adynodo_in_adypadre(nodoady_para_comparar, nodo)): #Si solo es amigo de nodo, o sus amigos son amigos de nodo: No hay nadie en sus adyacentes que se le pueda recomendar a nodo
				for nodoady in nodoady_para_comparar.adyacentes(): 				
					contador = 1 #Empieza en 1 porque ya contamos que es adyacente de nodoayd_para_comparar
					if (nodoady != nodo) and (nodoady not in adyacentes_de_nodo): #tiene que ser diferente de nodo y no tiene que ser amigo de nodo
						for nodo_ady in	nodoady.adyacentes(): 
							if (nodo_ady != nodoady_para_comparar) and (nodo_ady in adyacentes_de_nodo):
								contador+= 1
						if contador > contador_recomendado:
							contador_recomendado = contador
							nodo_recomendado = nodoady
		print  nodo.nombre() + ": " + nodo_recomendado.nombre() + "(" + str(contador_recomendado) + " amigos en común)"
		
def iniciar_programa():
	print "TP1 de Teoría de Algoritmos"
	while True:	
		try:			
			archivo=raw_input("Nombre del archivo a procesar: ")	
			break			
		except IOError:
			print "El archivo es inválido."	
	return archivo;
	

def main():
	archivo = iniciar_programa()		

	grafo = classgrafo.Grafo()
		
	classgrafo.Lector(archivo, grafo)
	
	if grafo.esta_vacio():
		return

	calcular_punto_1(grafo)

	calcular_punto_2(grafo)

	calcular_punto_3(grafo)

main()

